<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>BST二叉搜索树</title>
</head>

<body>
    <script>
        function TreeNode(val, left, right) {
            this.val = (val === undefined ? 0 : val)
            this.left = (left === undefined ? null : left)
            this.right = (right === undefined ? null : right)
        }

        var generateTrees = function (n) {
            function buildTree(start, end) {
                let _result = []
                // 指针交错递归终止
                if (start > end) return [null]
                // i指针滑动，枚举left和right分段的所有可能
                for (let i = start; i <= end; i++) {
                    // 左侧和右侧生成树的集合 返回为数组
                    let left = buildTree(start, i - 1)
                    let right = buildTree(i + 1, end)
                    // 循环左右两侧的树集合 分别拼接到新树上，并且存储到结果数组中
                    for (const leftNode of left) {
                        for (const rightNode of right) {
                            let node = new TreeNode(i)
                            node.left = leftNode
                            node.right = rightNode
                            console.log(node)
                            _result.push(node)
                        }
                    }
                }
                // 返回指定范围生成的树集合
                return _result
            }
            // n 为 0 是返回[]
            if (n === 0) return []
            // 指定最大范围
            return buildTree(1, n)
        }
        console.log(generateTrees(3))
    </script>
</body>

</html>